#pragma once

#include "vector.hpp"
#include "list.hpp"

namespace zuck
{
	template<typename T, typename Container = list<T>>
	class queue {
    private:
        using _Container = zuck::list<T>;
	public:
		using value_type	   = typename Container::value_type;
		using size_type		   = typename Container::size_type;
		using reference	       = typename Container::reference;
		using const_reference  = typename Container::const_reference;
		using rvalue_reference = typename Container::rvalue_reference;
	public:
		explicit queue()noexcept {}

		explicit queue(const Container& data) : _m_data(data) {}

		queue(const queue& other) : _m_data(other._m_data) {}

		queue(queue&& other)noexcept : _m_data(zuck::move(other._m_data)) {}

		~queue() { _m_data.~list(); }

		template<typename ...Args>
		emplace(Args&&... args)                    { _m_data.emplace_back(zuck::forward<Args>(args)...); }

		Container get_container()const              { return _m_data; }

		inline void swap(queue& other)noexcept      { _m_data.swap(other._m_data); }

		inline void push(value_type const& val)     { _m_data.push_back(val); }

		inline void push(value_type&& val)          { _m_data.push_back(val); }

		inline void pop()                           { _m_data.pop_front(); }

		[[nodiscard]] inline bool empty()const      { return _m_data.empty(); }

		[[nodiscard]] inline size_type size()const  { return _m_data.size(); }

		inline value_type& front()                  { return _m_data.front(); }

		inline value_type& tail()                   { return _m_data.back(); }

		inline queue& operator=(const queue& other)
		{
			_m_data = other._m_data;
			return *this;
		}

		inline queue& operator=(queue&& other)noexcept
		{
			_m_data = zuck::move(other._m_data);
			return *this;
		}
	private:
		Container _m_data{};
	};


	template<typename T, typename Container = list<T>>
	queue(Container const&)->queue<T, Container>;

	template<typename T, typename Container = list<T>>
	queue(queue<T, Container> const&)->queue<T, Container>;

	template<typename T, typename Container = list<T>>
	queue(queue<T, Container>&&)->queue<T, Container>;


// priority queue
	template<typename T, 
		typename Container = vector<T>, 
		typename _Compare  = less<typename Container::value_type>
	>
	class priority_queue {
	public:
		using container_type  = Container;
		using value_compare   = _Compare;
		using value_type	  = typename Container::value_type;
		using reference		  = typename Container::reference;
		using const_reference = typename Container::const_reference;
		using size_type		  = typename Container::size_type;
	private:
		Container	_data{};
		_Compare	_cmp;
		size_type	_cnt;
	public:
        explicit priority_queue() : _cnt(0) {}

		explicit priority_queue(Container const& _data)
            :_data(_data), _cnt(_data.size()) {}

		explicit priority_queue(_Compare const& _Cmp)
            : _cmp(_Cmp), _cnt(0) {}

		explicit priority_queue(Container const& data, _Compare const& cmp)
			: _data(data), _cmp(cmp), _cnt(0) {}

		explicit priority_queue(Container&& _data)
            :_data(zuck::move(_data)), _cnt(_data.size()) {}

		priority_queue(priority_queue const& _other) 
			: _data(_other._data), _cmp(_other._cmp), _cnt(_other._cnt)
            , _cnt(other.size()) {}
		
		priority_queue(priority_queue&& _other)noexcept
			: _data(_other._data), _cmp(_other._cmp), _cnt(_other._cnt) 
		{
			_other._data.clear();
			_other._cnt = 0;
		}

		~priority_queue() {}

		template<typename ...Args>
		void emplace(Args&&... args)
		{
			_data.push_back(zuck::forward<Args>(args)...);
		}

		void push(T&& _Obj)
		{
			if (empty()) {
				_data.resize(2);
				_data[1] = _Obj;
				++_cnt;
				return;
			}
			_data.push_back(_Obj);
			++_cnt;
			__AjustAfterPush();
			return;
		}

		[[nodiscard]] inline value_type top()noexcept { return _data[1]; }

		[[nodiscard]] inline bool empty()const noexcept
		{ 
			return static_cast<bool>(_cnt == 0);
		}

		[[nodiscard]] inline size_type size()const noexcept { return _cnt; }

		inline void swap(priority_queue& _Other) noexcept
		{
			_data.swap(_Other._data);
			_cnt ^= _Other._cnt ^= _cnt ^= _Other._cnt;
		}

		inline bool pop()noexcept {
			if (empty()) return false;
			_data[1] = _data[_cnt--];
			__AjustAfterPop();
			return true;
		}

		inline priority_queue& operator=(const priority_queue& _other)
		{
			_data = _other._data;
			_cmp = _other._cmp;
			return *this;
		}

		inline priority_queue& operator=(priority_queue&& _other)noexcept
		{
			_data = zuck::move(_other._data);
			_cnt = _other._cnt;
			_other._cnt = 0;
			return *this;
		}

	private:
		void __AjustAfterPush()
		{
			size_type _Ind = _cnt;

			for (; (_Ind >> 1) && _cmp(_data[_Ind >> 1], _data[_Ind]);) {
				zuck::swap(_data[_Ind >> 1], _data[_Ind]);
				_Ind >>= 1;
			}
		}

		void __AjustAfterPop()
		{
			size_type _Ind = 1;

			for (; (_Ind << 1) <= _cnt;) {
				size_type tmp = _Ind, l = (_Ind << 1), r = (_Ind << 1 | 1);
				if (_cmp(_data[tmp], _data[l])) {
					tmp = l;
				}
				if (r <= _cnt && _cmp(_data[tmp], _data[r])) {
					tmp = r;
				}
				if (tmp == _Ind) break;
				std::swap(_data[_Ind], _data[tmp]);
				_Ind = tmp;
			}
			return;
		}
	};
}

